木（Tree）とは、非線形な階層的データ構造であり、ファイルシステムや家系図といった現実世界の組織構造を模倣しています。リスト、スタック、キューのような線形配置とは異なり、木の本質はその階層性（階層的）と再帰性（再帰的）にあります。
1. 木の構造を解明する
- ノード（ノード）：キー（Key）と有効荷重を含む基本単位。
- ルートノード（ルートノード）：唯一の入力辺を持たないノードであり、木の出発点です。
- エッジ（エッジ）：ノードを結ぶ唯一の経路であり、親子関係を表します。
- 葉ノード（葉ノード）：子ノードを持たない末端であり、再帰の終了条件として自然な境界を形成します。
2. 再帰的定義による二つの視点
木は以下の二つの視点から理解できます：
グラフィックスの視点
ノードとエッジで構成される無環かつ連結なグラフであり、各ノード（ルートを除く）は一つの親ノードのみを持ちます。
ノードとエッジで構成される無環かつ連結なグラフであり、各ノード（ルートを除く）は一つの親ノードのみを持ちます。
再帰的視点
木は空であるか、または根ノードとゼロ個以上の部分木（サブツリー）から構成されます。
木は空であるか、または根ノードとゼロ個以上の部分木（サブツリー）から構成されます。
HTML DOMツリーの例
HTMLでは、
<html> がルートであり、<body> および <head> は兄弟ノードです。各タグとそのネストされたコンテンツはまとめて部分木を構成します。この構造により、 <ul> およびそのすべての <li> を全体として移動しても内部の階層構造は崩れません。